package com.example.demo.algorithm.lru_lfu;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * 使用双向链表和哈希表进行实现，哈希表用于存储对应的数据，双向链表用于数据被使用的时间先后顺序。
 * 1.在访问数据时，如果数据已存在缓存中，则把该数据的对应节点移到链表尾部。如此操作，在链表头部的节点则是最近最少使用的数据。
 * 2.当需要添加新的数据到缓存时，如果该数据已存在缓存中，则把该数据对应的节点移到链表尾部；如果不存在，则新建一个对应的节点，放到链表尾部；如果缓存满了，则把链表头部第一个节点和对应的数据删除。
 * @param <K>
 * @param <V>
 */
public class MyLruCache <K,V>{
    class Node{
        K key;
        V value;
        Node pre;
        Node next;

        Node(K key,V value){
            this.key = key;
            this.value = value;
        }
    }



    private int capacity;
    private Node head;
    private Node tail;
    /**
     * key和数据的映射
     */
    private Map<K,Node> map;

    MyLruCache(int capacity){
        this.capacity = capacity;
        map = new HashMap<>(4);
    }

    public V put(K key,V value){
        Node node = map.get(key);
        //有值，将值移动到队尾
        if(!Objects.isNull(node)){
            V oldValue = node.value;
            //更新数据
            node.value = value;
            moveToTail(node);
            return oldValue;
        }else{
            Node newNode = new Node(key,value);
            //数据不存在，判断链表是否满
            if(map.size() == capacity){
                //慢了就移除
                map.remove(removeHead().key);
            }
            //放入队尾节点
            addToTail(newNode);
            map.put(key,newNode);
            return null;
        }
    }

    public V get(K key){
        Node node = map.get(key);
        if(Objects.nonNull(node)){
            moveToTail(node);
            return node.value;
        }
        return null;
    }

    private void addToTail(Node newNode) {
        if(newNode == null){
            return;
        }
        if(head == null){
            head = newNode;
            tail = newNode;
        }else{
            //链接方式
            tail.next =  newNode;
            newNode.pre= tail;
            tail = newNode;
        }
    }

    private Node removeHead() {
        if(head == null) {
            return null;
        }

        Node res = head;
        if(head == tail){
            head = null;
            tail = null;
        }else{
            head = res.next;
            head.pre = null;
            res.next = null;
        }
        return res;
    }

    private void moveToTail(Node node) {
        if(tail == node){
            return;
        }
        if(head == node){
            head = node.next;
            head.pre = null;
        }else{
            //调整双向链表指针
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        node.pre = tail;
        node.next = null;
        tail.next = node;
        tail = node;
    }
}